/**
 * Exercise 9.64
 * -----------------------------------------------------------------------------
 * Implement `change priority` and `delete` for binomial queues.
 * Note: You will need to add a third link, which points up the tree, to the nodes.
 * -----------------------------------------------------------------------------
 */
#include <assert.h>
#include <stdlib.h>

typedef char Item;
typedef struct PQnode* PQlink;
typedef struct pq* PQ;

struct PQnode {
    Item key;
    PQlink l;
    PQlink r;
    PQlink p;
};

struct pq {
    PQlink *bq;
};

#define maxBQsize 4
#define test(C, B, A) 4*(C) + 2*(B) + 1*(A)
#define MAX_CHAR 127
#define key(A) (A)
#define less(A,B) (key(A) < key(B))
#define exch(A, B) { Item t = A; A = B; B = t; }

static PQlink z = NULL;

///////////////////////////////////辅助函数/////////////////////////////////
PQlink pair(PQlink p, PQlink q);
void BQjoin(PQlink *a, PQlink *b);
void fixUp(PQlink x);
void fixDown(PQlink x);
/////////////////////////////////接口操作////////////////////////////////////
PQ PQinit();
PQlink PQinsert(PQ pq, Item v);
void PQjoin(PQ a, PQ b);
Item PQdelmax(PQ pq);
void PQchange(PQ pq, PQlink x, Item v);
void PQdelete(PQ pq, PQlink x);
//////////////////////////////////测试用例/////////////////////////////////
void test_insert();
void test_change_priority();
void test_delete();

int main(int argc, char *argv[]) {
    test_change_priority();
    test_delete();
    return 0;
}
///////////////////////////////////辅助函数/////////////////////////////////
PQlink pair(PQlink p, PQlink q) {
    if (p->key < q->key) {
        p->r = q->l;
        if (p->r != z) {
            p->r->p = p;
        }
        q->l = p;
        p->p = q;
        return q;
    }else {
        q->r = p->l;
        if (q->r != z) {
            q->r->p = q;
        }
        p->l = q;
        q->p = p;
        return p;
    }
}

void BQjoin(PQlink *a, PQlink *b) {
    int i;
    PQlink c = z;
    for (i = 0; i < maxBQsize; i++) {
        switch (test(c != z, b[i] != z, a[i] != z)) {
            case 2:
                a[i] = b[i];
                break;
            case 3:
                c = pair(a[i], b[i]);
                a[i] = z;
                break;
            case 4:
                a[i] = c;
                c = z;
                break;
            case 5:
                c = pair(c, a[i]);
                a[i] = z;
                break;
            case 6:
            case 7:
                c = pair(c, b[i]);
                break;
            default:
                break;
        }
    }
}
void fixUp(PQlink x) {
    while (x != z && x->p != z && x->key > x->p->key) {
        exch(x->key,x->p->key);
        x = x->p;
    }
}
void fixDown(PQlink x) {
    if (x == z) {
        return;
    }
    PQlink curr = x;
    while (curr != z) {
        PQlink max_child = z;
        PQlink child_iter = curr->l;
        while (child_iter != z) {
            if (max_child == z || less(max_child->key, child_iter->key)) {
                max_child = child_iter;
            }
            child_iter = child_iter->r;
        }
        if (max_child == z || max_child->key <= curr->key) {
            break;
        }
        exch(curr->key, max_child->key);
        curr = max_child;
    }
}

/////////////////////////////////接口操作////////////////////////////////////
PQ PQinit() {
    PQ pq = (PQ)malloc(sizeof(*pq));
    pq->bq = (PQlink *)malloc(maxBQsize * sizeof(PQlink));

    int i;
    for (i = 0; i < maxBQsize; i++) {
        pq->bq[i] = z;
    }

    return pq;
}

PQlink PQinsert(PQ pq, Item v) {
    PQlink t = malloc(sizeof(*t));
    t->key = v;
    t->l = z;
    t->r = z;

    PQ tempPQ = PQinit();
    tempPQ->bq[0] = t;

    PQjoin(pq, tempPQ);
    return t;
}

void PQjoin(PQ a, PQ b) {
    BQjoin(a->bq, b->bq);
}

Item PQdelmax(PQ pq) {
    int i;
    int max;
    PQlink x;
    Item v;
    PQlink temp[maxBQsize];

    for (i = 0, max = -1; i < maxBQsize; i++) {
        if (pq->bq[i] != z) {
            if ((max == -1) || (v < pq->bq[i]->key)) {
                max = i;
                v = pq->bq[max]->key;
            }
        }
    }

    x = pq->bq[max]->l;
    for (i = max; i < maxBQsize; i++) {
        temp[i] = z;
    }
    for (i = max; i > 0; i--) {
        temp[i-1] = x;
        x = x->r;
        temp[i-1]->r = z;
    }

    free(pq->bq[max]);
    pq->bq[max] = z;

    BQjoin(pq->bq, temp);
    return v;
}

void PQdelete(PQ pq, PQlink x) {
    PQchange(pq, x, MAX_CHAR);
    PQdelmax(pq);
}

void PQchange(PQ pq, PQlink x, Item v) {
    if (x == z) {
        return ;
    }
    Item old = x->key;
    x->key = v;

    if (v > old) {
        //向上修正
        fixUp(x);
    }else {
        //向下修正
        fixDown(x);
    }
}

///////////////////////////////////测试用例////////////////////////////////////////////////////
void test_insert() {
    PQ pq = PQinit();
    // E-A-S-Y-Q-U-E-S-T-I-O-N
    PQinsert(pq, 'E');
    PQinsert(pq, 'A');
    PQinsert(pq, 'S');
    PQinsert(pq, 'Y');
    PQinsert(pq, 'Q');
    PQinsert(pq, 'U');
    PQinsert(pq, 'E');
    PQinsert(pq, 'S');
    PQinsert(pq, 'T');
    PQinsert(pq, 'I');
    PQinsert(pq, 'O');
    PQinsert(pq, 'N');

    assert(pq->bq[0] == z);
    assert(pq->bq[1] == z);
    assert(pq->bq[2]->key == 'T');
    assert(pq->bq[2]->r == z);
    assert(pq->bq[2]->l->key == 'O');
    assert(pq->bq[2]->l->l->key == 'N');
    assert(pq->bq[2]->l->r->key == 'I');
    assert(pq->bq[3]->key == 'Y');
    assert(pq->bq[3]->r == z);
    assert(pq->bq[3]->l->key == 'U');
    assert(pq->bq[3]->l->l->key == 'S');
    assert(pq->bq[3]->l->r->key == 'E');
    assert(pq->bq[3]->l->l->l->key == 'E');
    assert(pq->bq[3]->l->l->r->key == 'Q');
    assert(pq->bq[3]->l->r->l->key == 'A');
    assert(pq->bq[3]->l->r->r->key == 'S');
}

void test_change_priority() {
    PQ pq = PQinit();
    // E-A-S-Y-Q-U-E-S-T-I-O-N
    PQinsert(pq, 'E');
    PQinsert(pq, 'A');
    PQinsert(pq, 'S');
    PQlink x = PQinsert(pq, 'Y');
    PQinsert(pq, 'Q');
    PQinsert(pq, 'U');
    PQinsert(pq, 'E');
    PQinsert(pq, 'S');
    PQinsert(pq, 'T');
    PQinsert(pq, 'I');
    PQinsert(pq, 'O');
    PQinsert(pq, 'N');

    PQchange(pq, x, 'B');

    assert(pq->bq[3]->key == 'U');
    assert(pq->bq[3]->l->key == 'S');
    assert(pq->bq[3]->l->l->key == 'E');
    assert(pq->bq[3]->l->l->l->key == 'B');


}
void test_delete() {
    PQ pq = PQinit();
    // E-A-S-Y-Q-U-E-S-T-I-O-N
    PQinsert(pq, 'E');
    PQinsert(pq, 'A');
    PQinsert(pq, 'S');
    PQinsert(pq, 'Y');
    PQinsert(pq, 'Q');
    PQinsert(pq, 'U');
    PQinsert(pq, 'E');
    PQinsert(pq, 'S');
    PQinsert(pq, 'T');
    PQlink del = PQinsert(pq, 'I');
    PQinsert(pq, 'O');
    PQinsert(pq, 'N');

    PQdelete(pq, del);

    assert(pq->bq[0]->key == 'O');
    assert(pq->bq[1]->key == 'T');
    assert(pq->bq[1]->l->key == 'N');
    assert(pq->bq[2] == z);
}